#include "heapSort.h"
#include "contador.h"
#include<stdio.h>
#include<stdlib.h>

void heapSort(int a[], int n,long cont[])
{
   int i = n/2, pai, filho;
   int t;
 
   for (;;)
   {      
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0)
             return;        
          cont[1]++;
          t = a[n];
          a[n] = a[0];
      }
     
      pai = i;
      filho = i*2 + 1;
 
      while (filho < n)
      {
          cont[0]++;  
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho])){
              filho++;
              
          }
          cont[0]++;
          if (a[filho] > t)
          {            
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;
             cont[1]++;
          }
          else
             break;
      }
      a[pai] = t;
      cont[1]++;
   }
}
